1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package com.google.common.collect;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19
20 import com.google.common.annotations.Beta;
21 import com.google.common.annotations.GwtIncompatible;
22 import com.google.common.annotations.VisibleForTesting;
23 import com.google.common.base.MoreObjects;
24
25 import java.util.Collection;
26 import java.util.Comparator;
27 import java.util.Iterator;
28 import java.util.Map.Entry;
29 import java.util.NavigableMap;
30 import java.util.NoSuchElementException;
31 import java.util.Set;
32 import java.util.TreeMap;
33
34 import javax.annotation.Nullable;
35
36
37
38
39
40
41
42 @Beta
43 @GwtIncompatible("uses NavigableMap")
44 public class TreeRangeSet<C extends Comparable<?>>
45 extends AbstractRangeSet<C> {
46
47 @VisibleForTesting
48 final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
49
50
51
52
53 public static <C extends Comparable<?>> TreeRangeSet<C> create() {
54 return new TreeRangeSet<C>(new TreeMap<Cut<C>, Range<C>>());
55 }
56
57
58
59
60 public static <C extends Comparable<?>> TreeRangeSet<C> create(RangeSet<C> rangeSet) {
61 TreeRangeSet<C> result = create();
62 result.addAll(rangeSet);
63 return result;
64 }
65
66 private TreeRangeSet(NavigableMap<Cut<C>, Range<C>> rangesByLowerCut) {
67 this.rangesByLowerBound = rangesByLowerCut;
68 }
69
70 private transient Set<Range<C>> asRanges;
71
72 @Override
73 public Set<Range<C>> asRanges() {
74 Set<Range<C>> result = asRanges;
75 return (result == null) ? asRanges = new AsRanges() : result;
76 }
77
78 final class AsRanges extends ForwardingCollection<Range<C>> implements Set<Range<C>> {
79 @Override
80 protected Collection<Range<C>> delegate() {
81 return rangesByLowerBound.values();
82 }
83
84 @Override
85 public int hashCode() {
86 return Sets.hashCodeImpl(this);
87 }
88
89 @Override
90 public boolean equals(@Nullable Object o) {
91 return Sets.equalsImpl(this, o);
92 }
93 }
94
95 @Override
96 @Nullable
97 public Range<C> rangeContaining(C value) {
98 checkNotNull(value);
99 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(Cut.belowValue(value));
100 if (floorEntry != null && floorEntry.getValue().contains(value)) {
101 return floorEntry.getValue();
102 } else {
103
104 return null;
105 }
106 }
107
108 @Override
109 public boolean encloses(Range<C> range) {
110 checkNotNull(range);
111 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
112 return floorEntry != null && floorEntry.getValue().encloses(range);
113 }
114
115 @Nullable
116 private Range<C> rangeEnclosing(Range<C> range) {
117 checkNotNull(range);
118 Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
119 return (floorEntry != null && floorEntry.getValue().encloses(range))
120 ? floorEntry.getValue()
121 : null;
122 }
123
124 @Override
125 public Range<C> span() {
126 Entry<Cut<C>, Range<C>> firstEntry = rangesByLowerBound.firstEntry();
127 Entry<Cut<C>, Range<C>> lastEntry = rangesByLowerBound.lastEntry();
128 if (firstEntry == null) {
129 throw new NoSuchElementException();
130 }
131 return Range.create(firstEntry.getValue().lowerBound, lastEntry.getValue().upperBound);
132 }
133
134 @Override
135 public void add(Range<C> rangeToAdd) {
136 checkNotNull(rangeToAdd);
137
138 if (rangeToAdd.isEmpty()) {
139 return;
140 }
141
142
143
144 Cut<C> lbToAdd = rangeToAdd.lowerBound;
145 Cut<C> ubToAdd = rangeToAdd.upperBound;
146
147 Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(lbToAdd);
148 if (entryBelowLB != null) {
149
150 Range<C> rangeBelowLB = entryBelowLB.getValue();
151 if (rangeBelowLB.upperBound.compareTo(lbToAdd) >= 0) {
152
153 if (rangeBelowLB.upperBound.compareTo(ubToAdd) >= 0) {
154
155 ubToAdd = rangeBelowLB.upperBound;
156
157
158
159
160 }
161 lbToAdd = rangeBelowLB.lowerBound;
162 }
163 }
164
165 Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(ubToAdd);
166 if (entryBelowUB != null) {
167
168 Range<C> rangeBelowUB = entryBelowUB.getValue();
169 if (rangeBelowUB.upperBound.compareTo(ubToAdd) >= 0) {
170
171 ubToAdd = rangeBelowUB.upperBound;
172 }
173 }
174
175
176 rangesByLowerBound.subMap(lbToAdd, ubToAdd).clear();
177
178 replaceRangeWithSameLowerBound(Range.create(lbToAdd, ubToAdd));
179 }
180
181 @Override
182 public void remove(Range<C> rangeToRemove) {
183 checkNotNull(rangeToRemove);
184
185 if (rangeToRemove.isEmpty()) {
186 return;
187 }
188
189
190
191
192 Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
193 if (entryBelowLB != null) {
194
195 Range<C> rangeBelowLB = entryBelowLB.getValue();
196 if (rangeBelowLB.upperBound.compareTo(rangeToRemove.lowerBound) >= 0) {
197
198 if (rangeToRemove.hasUpperBound()
199 && rangeBelowLB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
200
201 replaceRangeWithSameLowerBound(
202 Range.create(rangeToRemove.upperBound, rangeBelowLB.upperBound));
203 }
204 replaceRangeWithSameLowerBound(
205 Range.create(rangeBelowLB.lowerBound, rangeToRemove.lowerBound));
206 }
207 }
208
209 Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(rangeToRemove.upperBound);
210 if (entryBelowUB != null) {
211
212 Range<C> rangeBelowUB = entryBelowUB.getValue();
213 if (rangeToRemove.hasUpperBound()
214 && rangeBelowUB.upperBound.compareTo(rangeToRemove.upperBound) >= 0) {
215
216 replaceRangeWithSameLowerBound(
217 Range.create(rangeToRemove.upperBound, rangeBelowUB.upperBound));
218 }
219 }
220
221 rangesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
222 }
223
224 private void replaceRangeWithSameLowerBound(Range<C> range) {
225 if (range.isEmpty()) {
226 rangesByLowerBound.remove(range.lowerBound);
227 } else {
228 rangesByLowerBound.put(range.lowerBound, range);
229 }
230 }
231
232 private transient RangeSet<C> complement;
233
234 @Override
235 public RangeSet<C> complement() {
236 RangeSet<C> result = complement;
237 return (result == null) ? complement = new Complement() : result;
238 }
239
240 @VisibleForTesting
241 static final class RangesByUpperBound<C extends Comparable<?>>
242 extends AbstractNavigableMap<Cut<C>, Range<C>> {
243 private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
244
245
246
247
248
249 private final Range<Cut<C>> upperBoundWindow;
250
251 RangesByUpperBound(NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
252 this.rangesByLowerBound = rangesByLowerBound;
253 this.upperBoundWindow = Range.all();
254 }
255
256 private RangesByUpperBound(
257 NavigableMap<Cut<C>, Range<C>> rangesByLowerBound, Range<Cut<C>> upperBoundWindow) {
258 this.rangesByLowerBound = rangesByLowerBound;
259 this.upperBoundWindow = upperBoundWindow;
260 }
261
262 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
263 if (window.isConnected(upperBoundWindow)) {
264 return new RangesByUpperBound<C>(rangesByLowerBound, window.intersection(upperBoundWindow));
265 } else {
266 return ImmutableSortedMap.of();
267 }
268 }
269
270 @Override
271 public NavigableMap<Cut<C>, Range<C>> subMap(
272 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
273 return subMap(Range.range(
274 fromKey, BoundType.forBoolean(fromInclusive),
275 toKey, BoundType.forBoolean(toInclusive)));
276 }
277
278 @Override
279 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
280 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
281 }
282
283 @Override
284 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
285 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
286 }
287
288 @Override
289 public Comparator<? super Cut<C>> comparator() {
290 return Ordering.<Cut<C>>natural();
291 }
292
293 @Override
294 public boolean containsKey(@Nullable Object key) {
295 return get(key) != null;
296 }
297
298 @Override
299 public Range<C> get(@Nullable Object key) {
300 if (key instanceof Cut) {
301 try {
302 @SuppressWarnings("unchecked")
303 Cut<C> cut = (Cut<C>) key;
304 if (!upperBoundWindow.contains(cut)) {
305 return null;
306 }
307 Entry<Cut<C>, Range<C>> candidate = rangesByLowerBound.lowerEntry(cut);
308 if (candidate != null && candidate.getValue().upperBound.equals(cut)) {
309 return candidate.getValue();
310 }
311 } catch (ClassCastException e) {
312 return null;
313 }
314 }
315 return null;
316 }
317
318 @Override
319 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
320
321
322
323
324 final Iterator<Range<C>> backingItr;
325 if (!upperBoundWindow.hasLowerBound()) {
326 backingItr = rangesByLowerBound.values().iterator();
327 } else {
328 Entry<Cut<C>, Range<C>> lowerEntry =
329 rangesByLowerBound.lowerEntry(upperBoundWindow.lowerEndpoint());
330 if (lowerEntry == null) {
331 backingItr = rangesByLowerBound.values().iterator();
332 } else if (upperBoundWindow.lowerBound.isLessThan(lowerEntry.getValue().upperBound)) {
333 backingItr = rangesByLowerBound.tailMap(lowerEntry.getKey(), true).values().iterator();
334 } else {
335 backingItr = rangesByLowerBound.tailMap(upperBoundWindow.lowerEndpoint(), true)
336 .values().iterator();
337 }
338 }
339 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
340 @Override
341 protected Entry<Cut<C>, Range<C>> computeNext() {
342 if (!backingItr.hasNext()) {
343 return endOfData();
344 }
345 Range<C> range = backingItr.next();
346 if (upperBoundWindow.upperBound.isLessThan(range.upperBound)) {
347 return endOfData();
348 } else {
349 return Maps.immutableEntry(range.upperBound, range);
350 }
351 }
352 };
353 }
354
355 @Override
356 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
357 Collection<Range<C>> candidates;
358 if (upperBoundWindow.hasUpperBound()) {
359 candidates = rangesByLowerBound.headMap(upperBoundWindow.upperEndpoint(), false)
360 .descendingMap().values();
361 } else {
362 candidates = rangesByLowerBound.descendingMap().values();
363 }
364 final PeekingIterator<Range<C>> backingItr = Iterators.peekingIterator(candidates.iterator());
365 if (backingItr.hasNext()
366 && upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound)) {
367 backingItr.next();
368 }
369 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
370 @Override
371 protected Entry<Cut<C>, Range<C>> computeNext() {
372 if (!backingItr.hasNext()) {
373 return endOfData();
374 }
375 Range<C> range = backingItr.next();
376 return upperBoundWindow.lowerBound.isLessThan(range.upperBound)
377 ? Maps.immutableEntry(range.upperBound, range)
378 : endOfData();
379 }
380 };
381 }
382
383 @Override
384 public int size() {
385 if (upperBoundWindow.equals(Range.all())) {
386 return rangesByLowerBound.size();
387 }
388 return Iterators.size(entryIterator());
389 }
390
391 @Override
392 public boolean isEmpty() {
393 return upperBoundWindow.equals(Range.all())
394 ? rangesByLowerBound.isEmpty()
395 : !entryIterator().hasNext();
396 }
397 }
398
399 private static final class ComplementRangesByLowerBound<C extends Comparable<?>>
400 extends AbstractNavigableMap<Cut<C>, Range<C>> {
401 private final NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound;
402 private final NavigableMap<Cut<C>, Range<C>> positiveRangesByUpperBound;
403
404
405
406
407
408
409 private final Range<Cut<C>> complementLowerBoundWindow;
410
411 ComplementRangesByLowerBound(NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound) {
412 this(positiveRangesByLowerBound, Range.<Cut<C>>all());
413 }
414
415 private ComplementRangesByLowerBound(NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound,
416 Range<Cut<C>> window) {
417 this.positiveRangesByLowerBound = positiveRangesByLowerBound;
418 this.positiveRangesByUpperBound = new RangesByUpperBound<C>(positiveRangesByLowerBound);
419 this.complementLowerBoundWindow = window;
420 }
421
422 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> subWindow) {
423 if (!complementLowerBoundWindow.isConnected(subWindow)) {
424 return ImmutableSortedMap.of();
425 } else {
426 subWindow = subWindow.intersection(complementLowerBoundWindow);
427 return new ComplementRangesByLowerBound<C>(positiveRangesByLowerBound, subWindow);
428 }
429 }
430
431 @Override
432 public NavigableMap<Cut<C>, Range<C>> subMap(
433 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
434 return subMap(Range.range(
435 fromKey, BoundType.forBoolean(fromInclusive),
436 toKey, BoundType.forBoolean(toInclusive)));
437 }
438
439 @Override
440 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
441 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
442 }
443
444 @Override
445 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
446 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
447 }
448
449 @Override
450 public Comparator<? super Cut<C>> comparator() {
451 return Ordering.<Cut<C>>natural();
452 }
453
454 @Override
455 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
456
457
458
459
460
461
462
463
464
465 Collection<Range<C>> positiveRanges;
466 if (complementLowerBoundWindow.hasLowerBound()) {
467 positiveRanges = positiveRangesByUpperBound.tailMap(
468 complementLowerBoundWindow.lowerEndpoint(),
469 complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED).values();
470 } else {
471 positiveRanges = positiveRangesByUpperBound.values();
472 }
473 final PeekingIterator<Range<C>> positiveItr = Iterators.peekingIterator(
474 positiveRanges.iterator());
475 final Cut<C> firstComplementRangeLowerBound;
476 if (complementLowerBoundWindow.contains(Cut.<C>belowAll()) &&
477 (!positiveItr.hasNext() || positiveItr.peek().lowerBound != Cut.<C>belowAll())) {
478 firstComplementRangeLowerBound = Cut.belowAll();
479 } else if (positiveItr.hasNext()) {
480 firstComplementRangeLowerBound = positiveItr.next().upperBound;
481 } else {
482 return Iterators.emptyIterator();
483 }
484 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
485 Cut<C> nextComplementRangeLowerBound = firstComplementRangeLowerBound;
486
487 @Override
488 protected Entry<Cut<C>, Range<C>> computeNext() {
489 if (complementLowerBoundWindow.upperBound.isLessThan(nextComplementRangeLowerBound)
490 || nextComplementRangeLowerBound == Cut.<C>aboveAll()) {
491 return endOfData();
492 }
493 Range<C> negativeRange;
494 if (positiveItr.hasNext()) {
495 Range<C> positiveRange = positiveItr.next();
496 negativeRange = Range.create(nextComplementRangeLowerBound, positiveRange.lowerBound);
497 nextComplementRangeLowerBound = positiveRange.upperBound;
498 } else {
499 negativeRange = Range.create(nextComplementRangeLowerBound, Cut.<C>aboveAll());
500 nextComplementRangeLowerBound = Cut.aboveAll();
501 }
502 return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
503 }
504 };
505 }
506
507 @Override
508 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
509
510
511
512
513
514
515
516
517 Cut<C> startingPoint = complementLowerBoundWindow.hasUpperBound()
518 ? complementLowerBoundWindow.upperEndpoint()
519 : Cut.<C>aboveAll();
520 boolean inclusive = complementLowerBoundWindow.hasUpperBound()
521 && complementLowerBoundWindow.upperBoundType() == BoundType.CLOSED;
522 final PeekingIterator<Range<C>> positiveItr =
523 Iterators.peekingIterator(positiveRangesByUpperBound.headMap(startingPoint, inclusive)
524 .descendingMap().values().iterator());
525 Cut<C> cut;
526 if (positiveItr.hasNext()) {
527 cut = (positiveItr.peek().upperBound == Cut.<C>aboveAll())
528 ? positiveItr.next().lowerBound
529 : positiveRangesByLowerBound.higherKey(positiveItr.peek().upperBound);
530 } else if (!complementLowerBoundWindow.contains(Cut.<C>belowAll())
531 || positiveRangesByLowerBound.containsKey(Cut.belowAll())) {
532 return Iterators.emptyIterator();
533 } else {
534 cut = positiveRangesByLowerBound.higherKey(Cut.<C>belowAll());
535 }
536 final Cut<C> firstComplementRangeUpperBound =
537 MoreObjects.firstNonNull(cut, Cut.<C>aboveAll());
538 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
539 Cut<C> nextComplementRangeUpperBound = firstComplementRangeUpperBound;
540
541 @Override
542 protected Entry<Cut<C>, Range<C>> computeNext() {
543 if (nextComplementRangeUpperBound == Cut.<C>belowAll()) {
544 return endOfData();
545 } else if (positiveItr.hasNext()) {
546 Range<C> positiveRange = positiveItr.next();
547 Range<C> negativeRange =
548 Range.create(positiveRange.upperBound, nextComplementRangeUpperBound);
549 nextComplementRangeUpperBound = positiveRange.lowerBound;
550 if (complementLowerBoundWindow.lowerBound.isLessThan(negativeRange.lowerBound)) {
551 return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
552 }
553 } else if (complementLowerBoundWindow.lowerBound.isLessThan(Cut.<C>belowAll())) {
554 Range<C> negativeRange =
555 Range.create(Cut.<C>belowAll(), nextComplementRangeUpperBound);
556 nextComplementRangeUpperBound = Cut.belowAll();
557 return Maps.immutableEntry(Cut.<C>belowAll(), negativeRange);
558 }
559 return endOfData();
560 }
561 };
562 }
563
564 @Override
565 public int size() {
566 return Iterators.size(entryIterator());
567 }
568
569 @Override
570 @Nullable
571 public Range<C> get(Object key) {
572 if (key instanceof Cut) {
573 try {
574 @SuppressWarnings("unchecked")
575 Cut<C> cut = (Cut<C>) key;
576
577 Entry<Cut<C>, Range<C>> firstEntry = tailMap(cut, true).firstEntry();
578 if (firstEntry != null && firstEntry.getKey().equals(cut)) {
579 return firstEntry.getValue();
580 }
581 } catch (ClassCastException e) {
582 return null;
583 }
584 }
585 return null;
586 }
587
588 @Override
589 public boolean containsKey(Object key) {
590 return get(key) != null;
591 }
592 }
593
594 private final class Complement extends TreeRangeSet<C> {
595 Complement() {
596 super(new ComplementRangesByLowerBound<C>(TreeRangeSet.this.rangesByLowerBound));
597 }
598
599 @Override
600 public void add(Range<C> rangeToAdd) {
601 TreeRangeSet.this.remove(rangeToAdd);
602 }
603
604 @Override
605 public void remove(Range<C> rangeToRemove) {
606 TreeRangeSet.this.add(rangeToRemove);
607 }
608
609 @Override
610 public boolean contains(C value) {
611 return !TreeRangeSet.this.contains(value);
612 }
613
614 @Override
615 public RangeSet<C> complement() {
616 return TreeRangeSet.this;
617 }
618 }
619
620 private static final class SubRangeSetRangesByLowerBound<C extends Comparable<?>>
621 extends AbstractNavigableMap<Cut<C>, Range<C>> {
622
623
624
625
626 private final Range<Cut<C>> lowerBoundWindow;
627
628
629
630
631
632 private final Range<C> restriction;
633
634 private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
635 private final NavigableMap<Cut<C>, Range<C>> rangesByUpperBound;
636
637 private SubRangeSetRangesByLowerBound(Range<Cut<C>> lowerBoundWindow, Range<C> restriction,
638 NavigableMap<Cut<C>, Range<C>> rangesByLowerBound) {
639 this.lowerBoundWindow = checkNotNull(lowerBoundWindow);
640 this.restriction = checkNotNull(restriction);
641 this.rangesByLowerBound = checkNotNull(rangesByLowerBound);
642 this.rangesByUpperBound = new RangesByUpperBound<C>(rangesByLowerBound);
643 }
644
645 private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window) {
646 if (!window.isConnected(lowerBoundWindow)) {
647 return ImmutableSortedMap.of();
648 } else {
649 return new SubRangeSetRangesByLowerBound<C>(
650 lowerBoundWindow.intersection(window), restriction, rangesByLowerBound);
651 }
652 }
653
654 @Override
655 public NavigableMap<Cut<C>, Range<C>> subMap(
656 Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive) {
657 return subMap(Range.range(
658 fromKey, BoundType.forBoolean(fromInclusive), toKey, BoundType.forBoolean(toInclusive)));
659 }
660
661 @Override
662 public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive) {
663 return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
664 }
665
666 @Override
667 public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive) {
668 return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
669 }
670
671 @Override
672 public Comparator<? super Cut<C>> comparator() {
673 return Ordering.<Cut<C>>natural();
674 }
675
676 @Override
677 public boolean containsKey(@Nullable Object key) {
678 return get(key) != null;
679 }
680
681 @Override
682 @Nullable
683 public Range<C> get(@Nullable Object key) {
684 if (key instanceof Cut) {
685 try {
686 @SuppressWarnings("unchecked")
687 Cut<C> cut = (Cut<C>) key;
688 if (!lowerBoundWindow.contains(cut) || cut.compareTo(restriction.lowerBound) < 0
689 || cut.compareTo(restriction.upperBound) >= 0) {
690 return null;
691 } else if (cut.equals(restriction.lowerBound)) {
692
693 Range<C> candidate = Maps.valueOrNull(rangesByLowerBound.floorEntry(cut));
694 if (candidate != null && candidate.upperBound.compareTo(restriction.lowerBound) > 0) {
695 return candidate.intersection(restriction);
696 }
697 } else {
698 Range<C> result = rangesByLowerBound.get(cut);
699 if (result != null) {
700 return result.intersection(restriction);
701 }
702 }
703 } catch (ClassCastException e) {
704 return null;
705 }
706 }
707 return null;
708 }
709
710 @Override
711 Iterator<Entry<Cut<C>, Range<C>>> entryIterator() {
712 if (restriction.isEmpty()) {
713 return Iterators.emptyIterator();
714 }
715 final Iterator<Range<C>> completeRangeItr;
716 if (lowerBoundWindow.upperBound.isLessThan(restriction.lowerBound)) {
717 return Iterators.emptyIterator();
718 } else if (lowerBoundWindow.lowerBound.isLessThan(restriction.lowerBound)) {
719
720 completeRangeItr =
721 rangesByUpperBound.tailMap(restriction.lowerBound, false).values().iterator();
722 } else {
723
724 completeRangeItr = rangesByLowerBound.tailMap(lowerBoundWindow.lowerBound.endpoint(),
725 lowerBoundWindow.lowerBoundType() == BoundType.CLOSED).values().iterator();
726 }
727 final Cut<Cut<C>> upperBoundOnLowerBounds = Ordering.natural()
728 .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
729 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
730 @Override
731 protected Entry<Cut<C>, Range<C>> computeNext() {
732 if (!completeRangeItr.hasNext()) {
733 return endOfData();
734 }
735 Range<C> nextRange = completeRangeItr.next();
736 if (upperBoundOnLowerBounds.isLessThan(nextRange.lowerBound)) {
737 return endOfData();
738 } else {
739 nextRange = nextRange.intersection(restriction);
740 return Maps.immutableEntry(nextRange.lowerBound, nextRange);
741 }
742 }
743 };
744 }
745
746 @Override
747 Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator() {
748 if (restriction.isEmpty()) {
749 return Iterators.emptyIterator();
750 }
751 Cut<Cut<C>> upperBoundOnLowerBounds = Ordering.natural()
752 .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
753 final Iterator<Range<C>> completeRangeItr = rangesByLowerBound.headMap(
754 upperBoundOnLowerBounds.endpoint(),
755 upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED)
756 .descendingMap().values().iterator();
757 return new AbstractIterator<Entry<Cut<C>, Range<C>>>() {
758 @Override
759 protected Entry<Cut<C>, Range<C>> computeNext() {
760 if (!completeRangeItr.hasNext()) {
761 return endOfData();
762 }
763 Range<C> nextRange = completeRangeItr.next();
764 if (restriction.lowerBound.compareTo(nextRange.upperBound) >= 0) {
765 return endOfData();
766 }
767 nextRange = nextRange.intersection(restriction);
768 if (lowerBoundWindow.contains(nextRange.lowerBound)) {
769 return Maps.immutableEntry(nextRange.lowerBound, nextRange);
770 } else {
771 return endOfData();
772 }
773 }
774 };
775 }
776
777 @Override
778 public int size() {
779 return Iterators.size(entryIterator());
780 }
781 }
782
783 @Override
784 public RangeSet<C> subRangeSet(Range<C> view) {
785 return view.equals(Range.<C>all()) ? this : new SubRangeSet(view);
786 }
787
788 private final class SubRangeSet extends TreeRangeSet<C> {
789 private final Range<C> restriction;
790
791 SubRangeSet(Range<C> restriction) {
792 super(new SubRangeSetRangesByLowerBound<C>(
793 Range.<Cut<C>>all(), restriction, TreeRangeSet.this.rangesByLowerBound));
794 this.restriction = restriction;
795 }
796
797 @Override
798 public boolean encloses(Range<C> range) {
799 if (!restriction.isEmpty() && restriction.encloses(range)) {
800 Range<C> enclosing = TreeRangeSet.this.rangeEnclosing(range);
801 return enclosing != null && !enclosing.intersection(restriction).isEmpty();
802 }
803 return false;
804 }
805
806 @Override
807 @Nullable
808 public Range<C> rangeContaining(C value) {
809 if (!restriction.contains(value)) {
810 return null;
811 }
812 Range<C> result = TreeRangeSet.this.rangeContaining(value);
813 return (result == null) ? null : result.intersection(restriction);
814 }
815
816 @Override
817 public void add(Range<C> rangeToAdd) {
818 checkArgument(restriction.encloses(rangeToAdd), "Cannot add range %s to subRangeSet(%s)",
819 rangeToAdd, restriction);
820 super.add(rangeToAdd);
821 }
822
823 @Override
824 public void remove(Range<C> rangeToRemove) {
825 if (rangeToRemove.isConnected(restriction)) {
826 TreeRangeSet.this.remove(rangeToRemove.intersection(restriction));
827 }
828 }
829
830 @Override
831 public boolean contains(C value) {
832 return restriction.contains(value) && TreeRangeSet.this.contains(value);
833 }
834
835 @Override
836 public void clear() {
837 TreeRangeSet.this.remove(restriction);
838 }
839
840 @Override
841 public RangeSet<C> subRangeSet(Range<C> view) {
842 if (view.encloses(restriction)) {
843 return this;
844 } else if (view.isConnected(restriction)) {
845 return new SubRangeSet(restriction.intersection(view));
846 } else {
847 return ImmutableRangeSet.of();
848 }
849 }
850 }
851 }